package com.sjy.type;

/**
 * @program: ProgressiveHashMap
 * @description:
 * @author: 智慧的苏苏
 * @create: 2025-09-01 16:06
 **/


import java.util.Objects;

/**
 * Redis-like hash table with progressive rehash.
 * Key/Value 都用 Object，你也可以改成泛型 <K,V>（示例中保持简洁）。
 */
public class Dict {
    // 单个桶节点（拉链法）
    private static final class DictEntry {
        String key;
        Object value;
        DictEntry next;

        DictEntry(String k, Object v, DictEntry next) {
            this.key = k;
            this.value = v;
            this.next = next;
        }
    }

    // 单张表
    private static final class DictHt {
        DictEntry[] buckets;
        int used;       // 有效键数（注意是键，不是桶）
        int size;       // 桶总数（2 的幂）
        int mask;       // = size-1

        DictHt(int size) {
            this.size = size;
            this.mask = size - 1;
            this.buckets = new DictEntry[size];
            this.used = 0;
        }
    }

    // ============ 配置 ============
    private static final int INIT_SIZE = 4; // 最小 4（>=1 且为 2 的幂）
    private static final double LOAD_FACTOR = 1.0; // 超过则扩容（可调）
    private static final int DEFAULT_REHASH_STEPS_PER_OP = 1;

    // ============ 状态 ============
    private final DictHt[] ht = new DictHt[2]; // ht[0]=主；ht[1]=目标（rehash 时使用）
    private int rehashIdx = -1;              // -1 表示未 rehash

    public Dict() {
        ht[0] = new DictHt(INIT_SIZE);
        ht[1] = null;
    }

    // ============ 公共 API ============

    /**
     * 新增或覆盖：等价于 Redis 的 set（存在则覆盖）。
     */
    public void set(String key, Object value) {
        ensureCapacityForInsert();
        // 渐进式 rehash：每次写顺带搬一点
        rehashStep(DEFAULT_REHASH_STEPS_PER_OP);

        insertInternal(key, value, true); // allowOverwrite = true
    }

    /**
     * 仅新增：存在则返回 false，不覆盖。
     */
    public boolean add(String key, Object value) {
        ensureCapacityForInsert();
        rehashStep(DEFAULT_REHASH_STEPS_PER_OP);

        return insertInternal(key, value, false);
    }

    /**
     * 获取值；rehash 期间需要查两张表。
     */
    public Object get(String key) {
        if (key == null) return null;
        DictEntry e;
        int h;
        if (isRehashing()) {
            rehashStep(DEFAULT_REHASH_STEPS_PER_OP);
            // 查新表
            h = bucketIndex(ht[1], key);
            e = findInBucket(ht[1].buckets[h], key);
            if (e != null) return e.value;
        }
        // 查老表
        h = bucketIndex(ht[0], key);
        e = findInBucket(ht[0].buckets[h], key);
        return e == null ? null : e.value;
    }

    /**
     * 删除键；返回是否删除成功。
     */
    public boolean del(Object key) {
        if (key == null) return false;
        if (isRehashing()) rehashStep(DEFAULT_REHASH_STEPS_PER_OP);

        boolean removed = deleteFromTable(0, key);
        if (isRehashing()) {
            removed = deleteFromTable(1, key) || removed;
            // 如果老表清空了，收尾
            maybeFinishRehash();
        }
        return removed;
    }

    /**
     * 当前键数量（两表之和）。
     */
    public int size() {
        return ht[0].used + (isRehashing() ? ht[1].used : 0);
    }

    /**
     * 手动推进渐进式 rehash（例如在定时器或空闲时调用）。
     */
    public void rehashStep(int steps) {
        if (!isRehashing()) return;
        int moved = 0;
        while (moved < steps && isRehashing()) {
            // 跳过空桶
            while (rehashIdx < ht[0].size && ht[0].buckets[rehashIdx] == null) {
                rehashIdx++;
            }
            if (rehashIdx >= ht[0].size) {
                finishRehash();
                break;
            }
            // 迁移当前桶的所有节点到新表
            DictEntry e = ht[0].buckets[rehashIdx];
            while (e != null) {
                DictEntry next = e.next;
                int hNew = bucketIndex(ht[1], e.key);
                e.next = ht[1].buckets[hNew];
                ht[1].buckets[hNew] = e;
                ht[1].used++;
                ht[0].used--;
                e = next;
            }
            ht[0].buckets[rehashIdx] = null;
            rehashIdx++;
            moved++;
        }
        if (ht[0].used == 0) finishRehash();
    }

    /**
     * 简单打印（调试用）。
     */
    public String debugInfo() {
        return String.format("rehashing=%s, rehashIdx=%d, ht0(size=%d,used=%d), ht1(%s)",
                isRehashing(), rehashIdx,
                ht[0].size, ht[0].used,
                isRehashing() ? ("size=" + ht[1].size + ",used=" + ht[1].used) : "null");
    }

    // ============ 内部方法 ============

    public boolean isRehashing() {
        return rehashIdx != -1;
    }


    private void ensureCapacityForInsert() {
        // 如果正在 rehash，让插入落到 ht[1]，无需判断负载（Redis 同理）
        if (isRehashing()) return;

        double lf = (double) ht[0].used / ht[0].size;
        if (lf > LOAD_FACTOR) {
            // 扩容到下一个 2^n（至少 *2）
            int newSize = nextPow2(ht[0].size << 1);
            startRehash(newSize);
        }
    }

    private void startRehash(int newSize) {
        if (isRehashing()) return;
        ht[1] = new DictHt(newSize);
        rehashIdx = 0;
    }

    private void finishRehash() {
        // 完成：丢弃旧表，把新表变为老表
        ht[0] = ht[1];
        ht[1] = null;
        rehashIdx = -1;
    }

    private void maybeFinishRehash() {
        if (isRehashing() && ht[0].used == 0) finishRehash();
    }

    private int bucketIndex(DictHt t, Object key) {
        // 你可以替换为更强的 hash（如 xxhash/murmur），这里用 JDK 混合并与 mask
        int h = spread(Objects.hashCode(key));
        return h & t.mask;
    }

    private static int spread(int h) {
        // 仿照 ConcurrentHashMap 扩散
        h ^= (h >>> 16);
        return h;
    }

    private DictEntry findInBucket(DictEntry head, Object key) {
        for (DictEntry e = head; e != null; e = e.next) {
            if (Objects.equals(e.key, key)) return e;
        }
        return null;
    }

    private boolean deleteFromTable(int which, Object key) {
        DictHt t = ht[which];
        if (t == null) return false;
        int h = bucketIndex(t, key);
        DictEntry prev = null, cur = t.buckets[h];
        while (cur != null) {
            if (Objects.equals(cur.key, key)) {
                if (prev == null) t.buckets[h] = cur.next;
                else prev.next = cur.next;
                t.used--;
                return true;
            }
            prev = cur;
            cur = cur.next;
        }
        return false;
    }

    private boolean insertInternal(String key, Object value, boolean allowOverwrite) {
        // 选择写入的目标表：rehash 期间写 ht[1]；否则写 ht[0]
        DictHt t = isRehashing() ? ht[1] : ht[0];
        int h = bucketIndex(t, key);
        // 查是否存在
        for (DictEntry e = t.buckets[h]; e != null; e = e.next) {
            if (Objects.equals(e.key, key)) {
                if (allowOverwrite) {
                    e.value = value;
                    return true;
                } else {
                    return false; // 不允许覆盖
                }
            }
        }
        // 不存在则头插
        t.buckets[h] = new DictEntry(key, value, t.buckets[h]);
        t.used++;
        return true;
    }

    private static int nextPow2(int x) {
        // 返回 >= x 的最小 2 的幂
        if (x <= 1) return 1;
        int n = x - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n + 1);
    }

}

